package datastructure.sort.sortmethod;

/**
 * 快速排序
 * Created by tanlee on 2016/3/18.
 */
public class QuickSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        sort(a,0,a.length - 1);
    }

    /**
     * 递归的进行调用
     * @param a
     * @param start
     * @param end
     */
    private void sort(Comparable[] a,int start,int end){
        // 小于等于
        if(start >= end){
            return;
        }
        int position = getPositionBySelf(a,start,end);
//        int position = getPosition(a,start,end);
        sort(a,start,position - 1);
        sort(a,position + 1,end);
    }

    /**
     * 获取进行排序的位置
     * 同时进行交换 将该数字左边的数字都小于该数,右边都大于该数
     * @param a
     * @param start
     * @param end
     * @return
     */
    private int getPosition(Comparable[] a,int start,int end){
        int i = start,j = end + 1;
        Comparable v = a[start];
        while(true){
            while(less(v,a[++i])){
                if(i == end)
                    break;
            }
            while(less(a[--j],v)){
                if(j == start)
                break;
            }
            if(i >= j){
                break;
            }
            exchange(a,i,j);
        }
        exchange(a,start,j);
        return j;
    }

    /**
     * 自己理解的快速排序,核心就是找出比第一个标兵小的所有数,放在a[start]之后,
     * 然后最后再做一次交换,这样就能保证,第一个数的左边都是小于他的数,右边都是大于他的数
     * @param a
     * @param start
     * @param end
     * @return
     */
    private int getPositionBySelf(Comparable[]a,int start,int end){
        int index = start;
        for(int i=start+1;i<=end;i++){
            if(less(a[i],a[start])){
                index ++ ;
                exchange(a,i,index);
            }
        }
        exchange(a,index,start);
        return index;
    }
}
